package leetcode;

//找到未排序数组中的第K大的数据
public class FindMedian {

	public static void main(String[] args) {
		FindMedian object = new FindMedian();
		int[] arr = {3, 2, 1, 5, 6, 4, 9, -2};
		System.out.println(object.findKthLargest(arr, 4));
		
	}
	
	public int findKthLargest(int[] nums, int k) {
		if (nums == null || nums.length <= 0) {
			return -1;
		}
		int low = 0;
		int high = nums.length - 1;
		int middle = 0;
		while(low <= high){
			middle = partition(nums, low, high);
			System.out.println("middle: " + middle);
			for(int i = 0; i < nums.length; i++){
				System.out.print(nums[i] + "  ");
			}
			System.out.println();
			if(middle == nums.length - k){
				return nums[middle];
			}else if(middle < nums.length - k){
				low = middle + 1;
			}else{
				high = middle - 1;
			}
		}
		return 0;
	}
	
	//这个时间复杂度是O(n)的
	
//	In quickselect, as specified, we apply recursion on only one half of the partition.
	//where, cn = time to perform partition, where c is any constant(doesn't matter). 
//	T(n/2) = applying recursion on one half of the partition.
//			Since it's an average case we assume that the partition was the median.
//
//			As we keep on doing recursion, we get the following set of equation:
//	T(n/2) = cn/2 + T(n/4)
//	T(n/4) = cn/2 + T(n/8)
//			.
//			.
//			.
//	T(2) = c.2 + T(1)
//	T(1) = c.1 + ...
	
//	c(n + n/2 + n/4 + ... + 2 + 1) = c(2n)
	//最坏情况下可能导致O(n^2)
	//可以使用shuffle
	public int partition(int[] nums, int left, int right){
		if(left > right || right >= nums.length || left < 0){
			return left;
		}
		int start = left;
		int end = right - 1;
		int key = nums[right];
		while(start <= end){
			while(start <= end && nums[start] < key){
				start++;
			}
			while(start <= end && nums[end] >= key){
				end--;
			}
			if(start < end){
				swap(nums, start, end);
			}
		}
		swap(nums, start, right);
		return start;
	}
	
	public void swap(int[] nums, int i, int j){
		int temp = nums[i];
		nums[i] = nums[j];
		nums[j] = temp;
	}
}
